package com.agile.leetcode.map;

import java.util.ArrayList;
import java.util.List;

public class MyMapImpl<K,V> implements MyMap<K,V> {
    // 默认承载能力
    private static final int DEFAULT_INIT_CAPICILITY=1<<4;
    // 默认扩展因子
    private static final float DEFAULT_LOAD_FACTOR=0.75f;
    // 传入长度
    private int defaultSize;
    // 传入扩载因子
    private float defaultFactor;
    // 已经使用的长度
    private int entryUseSize;
    // map长度
    private int size=0;
    // 底层数组结构
    private Entry<K,V>[] table;
    @Override
    public V get(K k) {
        int index=hash(k)&(defaultSize-1);
        if (table[index]==null){
            return null;
        }else {
            Entry<K, V> entry = table[index];
            do {
                if (k==entry.getKey()||k.equals(entry.getKey())){
                    return entry.value;
                }
                entry=entry.next;
            }while (entry!=null);
        }
        return null;
    }

    @Override
    public V put(K k, V v) {
        V oldValue=null;
        //是否需要扩容
        if (entryUseSize>=defaultSize*defaultFactor){
            reSize(2*defaultSize);
        }
        // 创建索引
        int index = hash(k) & (defaultSize - 1);
        // 该索引没有元素
        if (table[index]==null){
            table[index]=new Entry<K,V>(k,v,null);
            ++entryUseSize;
            ++size;
        }else {
            //key存在，需要遍历
            Entry<K,V> entry=table[index];
            Entry<K,V> e=entry;
            while (e!=null){
                if (k==e.getKey()||k.equals(e.getKey())) {
                    oldValue = e.value;
                    e.value = v;
                    return oldValue;
                }else {
                   e= e.next;
                }
                // 将其放在链表的头部，没有进行排序
                table[index]=new Entry<K,V>(k,v,entry);
                //用量+1
                ++entryUseSize;
                ++size;
            }
        }
        return oldValue;
    }
    // 构造方法初始化容量和扩容因子
    public MyMapImpl(int defaultSize,float defaultFactor){
        this.defaultSize=defaultSize;
        this.defaultFactor=defaultFactor;
        table=new Entry[this.defaultSize];
    }
    public MyMapImpl(){
        this(DEFAULT_INIT_CAPICILITY,DEFAULT_LOAD_FACTOR);
    }

    class Entry<K,V> implements MyMap.Entry<K,V>{
        private K key;
        private V value;
        private Entry<K,V> next;
        //构造方法
        public Entry(){};
        //
        public Entry(K key,V value,Entry<K,V> next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }
    public  void reSize(int i){
        Entry[] newTable=new Entry[i];
        defaultSize=i;
        entryUseSize=0;
        reHash(newTable);
    }
    public void reHash(Entry<K,V>[] newTable){
        // 创建集合接收
        List<Entry<K,V>> entryList=new ArrayList<>();
        // 构造新的数组
        for (Entry<K, V> entry : table) {
            do {
                entryList.add(entry);
                entry=entry.next;
            }while (entry!=null);
        }
        if (newTable.length>0){
            table=newTable;
        }
        // 重新添加到数组中
        for (Entry<K, V> entry : entryList) {
            put(entry.getKey(),entry.getValue());
        }
    }
    private int hash(K k){
        int hashCode = k.hashCode();
        hashCode^=(hashCode>>>20)^(hashCode>>>12);
        return hashCode^=(hashCode>>>7)^(hashCode>>>4);
    }
    public int size(){
        return size;
    }
}
